perm filename NSF[DOC,BGB] blob
sn#049100 filedate 1973-06-15 generic text, type C, neo UTF8
COMMENT ā VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 PROPOSAL TO NSF - (Bernie Chern).
C00006 00003 iv. Object Representation from Physical Measurement,
C00010 00004 2. WHAT WE PROPOSE TO DO.
C00020 00005 Elements of a Geometric Modeling System (continued).
C00025 00006 Elements of a Geometric Modeling System (continued).
C00030 00007 Itemized Shopping List.
C00034 00008 3. PREVIOUS WORK AT STANFORD.
C00037 00009 4. RELATION TO WORK DONE ELSEWHERE.
C00042 00010 5. FACILITIES AT STANFORD A.I. LAB
C00043 ENDMK
Cā;
PROPOSAL TO NSF - (Bernie Chern).
Principal Investigator - John McCarthy.
Co Principal Investigator - Bruce Baumgart.
This is a request for a grant of XXX to support a two year
research program in computer aided mechanical drawing of three
dimensional objects.
OUTLINE
1. Ideas and work already done.
2. What we propose to do.
3. Previous work at Stanford.
4. Relation to work done elsewhere.
5. Facilities at Stanford AI Lab.
6. Budget.
1. IDEAS AND WORK ALREADY DONE.
The proposed work is based on the following ideas and work
already done:
i. Explicit Object Representation.
An effective way of obtaining drawings of three dimensional
objects is to derive the drawing from an explicit computer model of
the three dimensional object. The orthographic, isometric and
perspective projections of the objects are obtained automatically
from the three dimensional description; with the hidden lines of the
object either eliminated, dashed or thinned; and with the appro-
priate labels, dimensions, comments, and arrowheads indicated.
ii. Object Representation from Logical Description.
One convenient way of making an explicit computer model of
an object is to simulate the process of building the object; that is
the description of how to build an object is an implicit
representation of the object. For example it is more convenient to
describe Figure-1 implicitly as a cube with a regular five pointed
star shaped hole cut through it, than as a list of the locii of all
its vertices.
iii. Language Extension.
Rather than developing new languages for geometric modeling
and mechanical drawing, we believe it is best to extend the old
languages: FORTRAN, ALGOL and LISP. The elements of a language
extension include a new data types for the language, general low
level primitives for manipulating the new data types, and a
convenient set of particular high level operations. The division of
the work into high level operations defined in terms of low level
primitives is an important part of the design because it isolates
the data structure manipulating code.
iv. Object Representation from Physical Measurement,
Another way to get an explicit computer model of an object
is to derive it from measurements made on an actual physical object,
2D drawings, or pictures. For example, the physical object might be
a clay or wood model of the thing begin designed. We believe that
only the lack of appropriate software is preventing the use of
television cameras as an inexpensive, accurate, and automatic means
of entering graphical data into a computer.
V. Prejudice against pens for graphics input.
We believe that the use of pens: light pens, sonic pens,
Rand tablets, Lincoln Wands, mechanical pens, joy sticks and so on;
can be replaced to advantage by keyboard and video input. First,
adequate keyboard edit, control and language conventions should be
developed for cases where the pen is used as a glamorized stick for
pushing buttons. Pen based editing systems require a keyboard or
button box in any event, so we argue that an operator who can
control and alter a drawing with his hands always in the locality of
the keyboard will be more efficient than an operator who has to use
both a keyboard and a pen. Second, one current justifible use of
pens and tablets is for tracing an existing drawing into the
computer; we believe that video software can be developed to
automate this operation.
vi. Mechanical Simulation.
Information such as the degrees of freedom of motion are
included in the object description and can be used to get pictures
of objects in different positions, as is demonstrated in the
(enclosed) flip book animation of a mechanical arm turning a block
over. Mechanical information can also be used to constain the shape
of a part in its desired place; or to find the space potentially
occupied by a moving part.
vii. Photomeric Simulation.
Photometric information such as the location and nature of
light sources and the light scattering properties of the objects'
surfaces can be included in the model and used to compute the video
appearance of solid opaque objects.
2. WHAT WE PROPOSE TO DO.
We propose to represent and simulate solid objects in a
computer for the sake of mechanical design, mechanical drawing and
robotics. Our two year goal will be to automate as much as possible
the task of creating and altering three dimensional data structures
from which mechanical drawings can be derived; this work would also
be a step towards solving the problem of representing physical
objects for a robot. The overall project to date has been called
"geometric modeling" a term which we use to refer to our particular
combination of computer graphics, physical world modeling, image
processing and geometry. Accordingly, the details of the work we
propose doing will be presented in terms of the elements comprising
a Geometric Modeling System, GMS. (The reader interested only in an
itemized list of project goals is advice to skip to the end of this
section).
Like a computer, the four main elements of a geometric
modeling system are memory, process, input and output. Starting with
memory, there are the problems of representation (how to describe a
physical object); accessing (how to find a particular description by
name, by location, or by whether it is currently in view); and
efficiency (how to keep the size of storage space down and how to
dynamically allocate fast and slow memory resources).
The currently implemented explicit object representation is
based on polyhedron models of solid rigids objects. A simple object
called a body is defined by a surface shell composed of faces, edges
and vertices that satisfies the Euler equation, V - E + F = 2; such
polyhedron bodies are combined to form compound objects. At
present, curved objects are represented by approximating them using
a polyhedron composed of a sufficient number of flat polygonal
faces. We propose developing a representation for curved objects, by
elaborating our polyhedrons to include faces which are not
necessarily flat but are defined by a function. These non-flat
polyhedrons will be called manifolds, and additional processors
would be developed to generate, alter, smooth, and display them.
A final representation issue we would study is that of a
format for communication of three dimensional models between alien
modeling systems. We believe that developing a three dimensional
standard format for everybody is very premature; and that the best
one project can realistically expect to achieve (towards
standardization) is to establish and promulgate a reasonible way
that alein systems may communicate with the local system.
Elements of a Geometric Modeling System (continued).
The usual input devices to a geometric modeling system
include keyboards, light-pens, joy-sticks, buttons, cameras and
film scanners; of which the most important to this proposal is the
keyboard because it is currently the best device for language input.
Indeed, we believe we can demonstrate that a system based on
keyboards can do geometric control and editing better than a system
based on both a light pen and a keyboard.
To repeat, rather than developing new languages for
geometric modeling and mechanical drawing, we propose extending the
programming languages: FORTRAN, ALGOL and LISP. The elements of a
language extension include new data types (the "memory" of our
system); a general purpose micro language level of primitives and a
special purpose macro language level of operations.
The micro level of language extension is composed of a small
set of primitive functions that invoke the only subroutines allowed
to directly create and alter the data structure. All the geometric
processors, editors, input, output and higher language operations
are implemented in terms of these fewer than fifty primiitves. The
resaon for having a two level system, is to isolate and minimize the
amount of code that is necessarily dependent on the details of the
data format. Furthermore, it is possible to construct primitives
that are complete and general with repect to fundamental principles
in polyhedron topology and geometry. For example, we now have a set
of Euler primitives that can generate any Eulerian polyhedron (and
only Eulerian polyhedra); as well as a set of Euclidean primitives
for applying the group of Euclidean transformations. With more good
luck, we intend to isolate sets of primitives for mechanics,
manifolds, and image forming.
The macro level of language extension is comprised of
operations that make it convenient to simulate building a mechanical
model of an object. The present macro level includes an operation
for "sweeping" edges into faces, and faces into solids; an operation
for "glueing" surfaces together; an operation for passing "cutting"
planes thru an object; and a most powerful trio of operations for
forming the volume set union, intersection and difference of two
given polyhedrons. Since polyhedrons can be taken as either bounding
a finite solid volume or a finite empty volume; we have found it
convenient to draw some objects indirectly by building their holes
and intersecting the holes with their simple outer shape. Further
macro operations we propose to code would include more "imaginery"
ones for bending, constraining, filling, enveloping, and expanding
upon a skeleton; as well as some more "realistic" operations that
would model regular machine shop tools such as a lathe, punch and
milling machine; and machine building processes such as welding,
fastening and assembly.
Elements of a Geometric Modeling System (continued).
A third kind of language is that provided for edit and
control. The main differences between a powerful interactive
graphics editor and a powerful interactive graphics programming
language is that an editor carries along its working context
automatically so that most arguments and data do not have to be
explicitly named because they happen to be "at the top of the stack"
and are visibly intensified or otherwise indicated on the display
screen. The advantage of the interactive editor is that the user is
relieved of having to coin and call names of things, however the
disadvantage is that he can not develope subroutines of the power
available in a programming language which provides notation for
procedures, arguments, and variables. Rather than lose the speed and
convenience of editing, we plan to keep the programming language
level distinct from the control and edit language.
Besides language inputs, a geometric modeling system should
have a way of reading data that is already in graphical form. For
such graphical input, we propose using a televsion camera and
believe that a system with a few video image processing primitives
can allow using video as a routine computer graphics input media.
For example, we already have developed video intensity contouring to
rapidly provide the edges of an image in a form available for
graphics editing.
The third main element of a geometric modeling system is the
geometric processors. There are language processors, mechanical
simulators, locus solvers, image analysis and image synthesis,
including the process most peculiar to three dimensional drawing
which is hidden line (and surface) elimination. We have several
implementations of each of several hidden line elimination
algorithms; and we have reason to believe that further work on our
most recent design will yield a hidden eliminator that can handle
curved objects, generate shadows, use the coherence between
successive images, and still be fast without special purpose
hardware. Since the purpose of the processors just mentioned should
be sufficiently clear we shall skip detailing their algorithms and
implementation, although this will comprise the bulk of the work and
publication we propose to do.
The fourth and final element of a modeling system is the
output, which includes dynamic CRT display, video display, hardcopy
graphics, as well as magnetic tape. Although mundane, the numerical
object descriptions on conventional (non display) computer media
like magnetic tape is important in making the output of an
interactive display system available for further automatic
processing.
Itemized Shopping List.
Ignoring the overall system organization and fine details,
the goals of the proposed project are summarized in the following
shopping list:
Items partially in hand.
1. Representation of solid rigid three dimensional polyhedra.
2. Language extension of geometric primitives.
3. Language extension of object building operations.
4. Polyhedron object hidden line eliminator.
5. Geometric editor.
Items within one year's work.
6. Generation of mechanical drawings from geometric models.
7. Representation for curved objects.
8. Representation for flexible objects.
9. Video acquisition of two dimensional drawings.
10. Mechanical simulation and animation.
Second year and elective Items.
11. Generation of high quality mechanical drawings, such as
assembly drawings and cut away layout drawings.
12. Development of a remote display terminal version.
13. Development of a standard FORTRAN version.
14. Mechanical drawings for a special area of engineering;
(pipefitting, screw threading, mining, or whatever).
15. Hidden line elimination for curved objects.
Basic research items.
16. Video acquisition of three dimensional objects.
17. Photometric simulation - shadows, multiple light sources;
for generation of high quality video appearance.
Substantial work has already been done on the first five
items listed; so that the most pessimistic and conservative estimate
of our potential achivevements for the next two years should include
the documentation, publication and elaboration of the research work
already done. Our intermediate expectations include making
considerable progress and original contribution with respect to the
first five items as well as being able to get a substantial start on
items numbered six through ten; as well as doing one of the five
items numbered eleven through fifteen. Finally, our optimistic
expectation would be to finish everything though item fifteen, and
to have started work on getting a system that could reduce live
video input into a mechanical model and that could output realistic
looking video from a mechanical model.
3. PREVIOUS WORK AT STANFORD.
This proposal is based on work by Bruce G. Baumgart as a
graduate student. Mr. Baumgart expects to complete his dissertation
entitled "Geometric Vision" in December 1973 and will continue as a
research associate on receiving his degree.
This work includes GEOMED, a Geometric Editor, which would
be the prototype of the mechanical drawing system we propose to
build. GEOMED is a 3D drawing program (controled solely by
keyboard); that can construct arbitrary polyhedral objects and
display them with hidden lines eliminated. GEOMED also accepts
CRE-images (explained below) and can form a polyhedron model
consistent with such images.
The subroutines and data structures of GEOMED have been
embedded in LISP and SAIL (Stanford Algol) to provide a geometric
language for physical world modeling and physical action simulation.
The embedded versions of GEOMED fall short of being language
extensions in that adequate syntax and flexible memory allocation is
currently lacking.
The image processing part of Mr. Baumgart's work lies in a
program named CRE, standing for Contour, Region, Edge image
representation. CRE converts a sequence of digital television
images into a contour edge data structure for interpretation by
other programs. Finally, there is TVFONT, which is a version of CRE
for making type font bit arrays from television images, or for
rescaling existing fonts.
4. RELATION TO WORK DONE ELSEWHERE.
The work proposed here has been strongly influenced by the
pioneering computer graphics work of Larry Roberts, Steven Coons and
Ivan Sutherland done at Massachusetts Institute of Technology,
Lincoln Laboratory, and Harvard University; as well as the more
recent work of Sutherland, Evans, Warnock, Watkins, X, Y, and Z at
the University of Utah. In fact, Mr. Baumgart did his undergraduate
thesis (at Harvard, 1968) with Prof. Sutherland, on development of a
three dimensional display system which was subsquently moved to
Utah. However, recent research work at Utah has been directed more
to the development of special purpose display hardware rather than
to the representation and input of three dimensional models.
Another major influence on the proposed work has been the
research in Artificial Intelligence, Computer Vision, Programming
Languages and Time Sharing done at Stanford University,
Massachusetts Institute of Technology and Stanford Research Institute.
Several interactive three dimensional drawing programs have
been written over the last ten years; however the genre is still
steeped in poorly understood data structures and algorithms, with
problems compounded by changing display hardware technology and
changing system environments.
3D sketchpad
X's thing at the University of Illinois.
Appel with IBM at Yorktown.
Lockheed
General Electric - flight simulators & display hardware.
Military - flight simulators.
NASA
Distinguish commerical 2D graphics and automatic drafting (Cal Comp,
Gerber, etc) from 3D design and mechanical drawing (General Motors
Research Laboratories - DAC System).
Finally, there are many commercially available engineering
programs that generate mechanical drawings for particular
applications. For example, the Control Data Corporation, has a
system that does structural steel detailing and that produces
graphics in accord with the drawing standards of the American Steel
Association. Such special purpose drawing programs require input
decks specifying the exact shape, dimensions and location of each
steel beam and are larger prepared by hand. A flexible interactive
three dimensional design program, such as the one we propose
creating, would be able to allow interactive design and
specification of steel structures; programing of operators for
handling steeling structures; and (in effect) FORMAT statements
which would allow outputing the special particular data required
by an existing programs.
5. FACILITIES AT STANFORD A.I. LAB
1. Time Sharing System - its relevance.
2. III displays
3. Data Disc displays.
4. XGP printer
5. Output for FR-80.
6. BUDGET
1. Baumgart
2. A programmer.
3. A graduate student.
4. Two high quality display terminals.
e.g. Systems concept's best.